package com.explorati.tree.LeetCode437.pathSum3;

import com.explorati.tree.LeetCode437.pathSum3.Solution.TreeNode;

public class Solution1 {
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	// 在以root为根的二叉树中，寻找和为sum的路径，返回这样的路径的个数
	public int pathSum(TreeNode root, int sum) {
		if (root == null) {
			return 0;
		}
		return findPath(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);

	}

	private int findPath(TreeNode node, int sum) {
		if (node == null) {
			return 0;
		}
		int res = 0;
		if (node.val == sum) {
			res += 1;
		}
		res += findPath(node.left, sum - node.val);
		res += findPath(node.right, sum - node.val);
		return res;
	}
}
